//
// Created by zhou on 2021/11/26.
//
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    bool isValid(string s) {
        stack<char> stack1;
        int len=s.length();
        if(len%2!=0)return false;
        for(int i=0;i<len;i++) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                stack1.push(s[i]);
            }
            else {
                if(stack1.empty())return false;
                char m=stack1.top();
                if((m=='('&&s[i]==')')||(m=='['&&s[i]==']')||(m=='{'&&s[i]=='}'))
                {
                    stack1.pop();
                }
                else return false;
            }
        }
        if(stack1.empty())return true;
        else return false;
    }
};
int main(){
    Solution solution;
    string s="(){}()";
    cout<<solution.isValid(s);
}